#include "DijkstraAlgorithms.h"
#include "Generators.h"
#include <vector>
#include <algorithm>
#include <stdexcept>



void graphesAdjacentWeighCheck(const WeighGraph& G, const std::vector<WeighEdge>& edgesList){
	int vertexNum = G.getVertexNum();
	std::set<WeighEdge> edgesSet;
	std::map<Edge, int> setOfMergedEdges;
	for (auto currentEdge : edgesList){
		Edge currentUnweighedEdge = currentEdge.getUnweighedEdge();
		if (setOfMergedEdges.count(currentUnweighedEdge) == 0)
			setOfMergedEdges[currentUnweighedEdge] = currentEdge.getWeight();
		else{
			int currentWeight = setOfMergedEdges[currentUnweighedEdge];
			setOfMergedEdges[currentUnweighedEdge] = std::min<int>(currentEdge.getWeight(), currentWeight);
		}
	}
	for (auto currentEdge : edgesList){
		edgesSet.insert(currentEdge);
	}
	
	std::set<WeighEdge> edgesFromAdjacentLists;
	for (int currentVertex = 0; currentVertex < vertexNum; ++currentVertex){
		std::vector<WeightAdjacent> adjacentList = G.getAdjacentWeights(currentVertex);
		for (auto toVertex : adjacentList){
			WeighEdge currentEdge = { currentVertex, toVertex.toVertex, toVertex.weight };
			if (edgesSet.count(currentEdge) == 0){
				throw std::logic_error("Extra edges in adjacent list of weigh graph");
			}
			edgesFromAdjacentLists.insert(currentEdge);
		}
	}
	for (auto currentEdge : edgesSet){
		if (edgesSet.count(currentEdge) == 0){
			throw std::logic_error("There isn't enough edges in weigh graph");
		}
	}
}

void weighGraphesUnitAdjacentCheck(){
	{
		int vertexNum = 0;
		int edgesNum = 0;
		std::vector<WeighEdge >edgesList;
		WeighGraph G(vertexNum, edgesList);
		graphesAdjacentWeighCheck(G, edgesList);
	}
	{
		int vertexNum = 100;
		int edgesNum = 0;
		std::vector<WeighEdge >edgesList;
		WeighGraph G(vertexNum, edgesList);
		graphesAdjacentWeighCheck(G, edgesList);
	}
	{
		int vertexNum = 4;
		int edgesNum = 2;
		std::vector<WeighEdge >edgesList{ { 0, 1 ,3}, { 2, 3 ,5 } };
		WeighGraph G(vertexNum, edgesList);
		graphesAdjacentWeighCheck(G, edgesList);
	}
	{
		int vertexNum = 10;
		int edgesNum = 15;
		std::vector<WeighEdge >edgesList;
		for (int currentVertex = 0; currentVertex < vertexNum; ++currentVertex){
			edgesList.push_back({ currentVertex, (currentVertex + 1) % vertexNum, getRandomPositiveNumber() });
		}
		for (int currentVertex = 0; currentVertex < 5; ++currentVertex){
			edgesList.push_back({ currentVertex, currentVertex + 5 , currentVertex + 1000});
		}
		WeighGraph G(vertexNum, edgesList);
		graphesAdjacentWeighCheck(G, edgesList);
	}

}

void stressAdjacentWeighCheck(){
	for (int testNumber = 0; testNumber < 50; ++testNumber){
		int vertexNum;
		std::vector<WeighEdge> edgesList;
		if (testNumber < 40)
			generateScriptForWeighGraph(vertexNum, edgesList, SMALL);
		else
			generateScriptForWeighGraph(vertexNum, edgesList, LARGE);
		WeighGraph G(vertexNum, edgesList);
		graphesAdjacentWeighCheck(G, edgesList);
	}
}

std::vector<int> getDistanceFromVertex(const WeighGraph& G, int vertex){
	int infinity = 1000000000;
	int vertexNum = G.getVertexNum();
	std::vector<std::vector<int> > floydDistance(vertexNum, std::vector<int>(vertexNum, infinity));
	for (int currentVertex = 0; currentVertex < vertexNum; ++currentVertex){
		floydDistance[currentVertex][currentVertex] = 0;
	}
	for (int currentVertex = 0; currentVertex <vertexNum; ++currentVertex){
		std::vector<WeightAdjacent> adjacentList = G.getAdjacentWeights(currentVertex);
		for (auto currentEdge: adjacentList){
			if (currentEdge.toVertex != currentVertex)
				floydDistance[currentVertex][currentEdge.toVertex] = currentEdge.weight;
		}
	}
	for (int middleVertex = 0; middleVertex < vertexNum; ++middleVertex){
		for (int fromVertex = 0; fromVertex < vertexNum; ++fromVertex){
			for (int toVertex = 0; toVertex < vertexNum; ++toVertex){
				floydDistance[fromVertex][toVertex] =
					std::min<int>(floydDistance[fromVertex][toVertex],
					floydDistance[fromVertex][middleVertex] + floydDistance[middleVertex][toVertex]);
			}
		}
	}
	return floydDistance[vertex];
}



std::vector<int> interfaceFindingDistance(int vertexNum, int startVertex,  const std::vector<WeighEdge>& edgesList){
	WeighGraph G(vertexNum, edgesList);
	SimpleDijkstraVisitor userClass(vertexNum);
	dijkstraAlgorithm(G, &userClass, startVertex);
	return userClass.getDistances();
}

std::vector<int> interfaceFindingPath(int vertexNum, int startVertex,  int fromVertex, const std::vector<WeighEdge>& edgesList){
	WeighGraph G(vertexNum, edgesList);
	SimpleDijkstraVisitor userClass(vertexNum);
	dijkstraAlgorithm(G, &userClass, startVertex);
	return userClass.getPathToVertex(fromVertex);
}

void unitDistanceCheck(){
	if (interfaceFindingDistance(1, 0, {}) != std::vector<int>{0}){
		throw std::logic_error("Wrong answer on unit test 1");
	}
	if (interfaceFindingDistance(2, 0, std::vector<WeighEdge>{ { 0, 1, 1 }, { 0, 1, 2 } }) != std::vector<int>{0, 1}){
		throw std::logic_error("Wrong answer on unit test 2");
	}
	if (interfaceFindingDistance(3, 0, std::vector<WeighEdge>{ WeighEdge{ 0, 1, 1 }, WeighEdge{ 1, 2, 1 }, WeighEdge{ 0, 2, 3 } }) != std::vector<int>{0, 1, 2}){
		throw std::logic_error("Wrong answer on unit test 3");
	}
	if (interfaceFindingDistance(3, 2, std::vector<WeighEdge>{{0, 1, 1}, { 1, 2, 1 }, { 2, 0, 1 }}) != std::vector<int>{1, 2, 0}){
		throw std::logic_error("Wrong answer on unit test 4");
	}
}

void stressDistanceCheck(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		int vertexNum;
		std::vector<WeighEdge> edgesList;
		generateScriptForWeighGraph(vertexNum, edgesList, SMALL);
		WeighGraph G(vertexNum, edgesList);
		std::vector<int> expectedDistanceList = getDistanceFromVertex(G, 0);
		SimpleDijkstraVisitor userClass(vertexNum);
		dijkstraAlgorithm(G, &userClass, 0);
		std::vector<int> getAnswer = userClass.getDistances();
		if (getAnswer != expectedDistanceList){
			throw std::logic_error("Wrong answer on random distance check");
		}	
	}
}

bool checkPath(const WeighGraph& G, int vertex, int distance, const std::vector<int> & path){
	if (path.front() != 0){
		throw std::logic_error("There is bad start vertex");
	}
	if (path.back() != vertex){
		throw std::logic_error("There is bad end vertex");
	}
	int lengthOfPath = 0;
	for (size_t currentSegment = 0; currentSegment < path.size() - 1; ++currentSegment){
		Edge curedge;
		lengthOfPath += G.getEdgeWeight(Edge(path[currentSegment], path[currentSegment + 1]));
	}
	if (lengthOfPath != distance){
		throw std::logic_error("There is not shortest path");
	}

}

void unitPathCheck(){
	if (interfaceFindingPath(1, 0, 0, {}) != std::vector<int>{0}){
		throw std::logic_error("Wrong answer on unit test path 1");
	}
	if (interfaceFindingPath(3, 0, 2, std::vector<WeighEdge>{{0, 1, 1}, { 1, 2, 1 }, { 0, 2, 3 } })
		!= std::vector<int>{0, 1, 2}){
		throw std::logic_error("Wrong answer on unit test path 2");
	}
	if (interfaceFindingPath(3, 0, 2, std::vector<WeighEdge>{{0, 1, 1}, { 1, 2, 1 }, { 0, 2, 1 } })
		!= std::vector<int>{0, 2}){
		throw std::logic_error("Wrong answer on unit test path 3");
	}
	if (interfaceFindingPath(3, 2, 1, std::vector<WeighEdge>{{0, 1, 1}, { 1, 2, 1 }, { 2, 0, 1 }})
		!= std::vector<int>{2, 0, 1}){ 
		throw std::logic_error("Wrong answer on unit test path 4");
	}
}

void stressPathCheck(){
	for (int testNumber = 0; testNumber < 70; ++testNumber){
		int vertexNum;
		std::vector<WeighEdge> edgesList;
		if (testNumber < 50)
			generateScriptForWeighGraph(vertexNum, edgesList, SMALL);
		else
			generateScriptForWeighGraph(vertexNum, edgesList, LARGE);
		WeighGraph G(vertexNum, edgesList);
		SimpleDijkstraVisitor userClass(vertexNum);
		dijkstraAlgorithm(G, &userClass, 0);
		std::vector<int> distance = userClass.getDistances();
		for (int stepTest = 0; stepTest < 10; ++stepTest){
			int currentVertex = getRandomPositiveNumber() % vertexNum;
			if (distance[currentVertex] != userClass.INFINITY_DISTANCE_){
				std::vector<int> path = userClass.getPathToVertex(currentVertex);
				checkPath(G, currentVertex, distance[currentVertex], path);
			}
		}
	}
}

